#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    string intToRoman(int num)
    {
        string roman_num = "";
        if (num >= 1000) {
            int count = num / 1000;
            for (int i = 0; i < count; i++)
                roman_num += 'M';
            num %= 1000;
        }
        if (num >= 100) {
            if (num / 100 == 9)
                roman_num += "CM";
            else if (num / 100 == 4)
                roman_num += "CD";
            else {
                if (num >= 500) {
                    roman_num += 'D';
                    num %= 500;
                }
                int count = num / 100;
                for (int i = 0; i < count; i++)
                    roman_num += 'C';
            }
            num %= 100;
        }
        if (num >= 10) {
            if (num / 10 == 9)
                roman_num += "XC";
            else if (num / 10 == 4)
                roman_num += "XL";
            else {
                if (num >= 50) {
                    roman_num += 'L';
                    num %= 50;
                }
                int count = num / 10;
                for (int i = 0; i < count; i++)
                    roman_num += 'X';
            }
            num %= 10;
        }
        if (num >= 1) {
            if (num == 9)
                roman_num += "IX";
            else if (num == 4)
                roman_num += "IV";
            else {
                if (num >= 5) {
                    roman_num += 'V';
                    num %= 5;
                }
                for (int i = 0; i < num; i++)
                    roman_num += 'I';
            }
        }
        return roman_num;
    }
};

int main(int argc, char const* argv[])
{
    Solution temp;
    cout << temp.intToRoman(3) << endl;
    cout << temp.intToRoman(4) << endl;
    cout << temp.intToRoman(9) << endl;
    cout << temp.intToRoman(58) << endl;
    cout << temp.intToRoman(1994) << endl;
    return 0;
}